package stack.convertPolandExpression;

import stack.stackDefine.MyArrayListStack;

import java.util.Arrays;
import java.util.List;
/**
 * 前置操作 ：直接对字符串操作，需要index遍历，把String变成一个List<String>数组更简介
 * 中缀转后缀步骤：
 *      1）初始化二个栈：运算符栈operStack和结果栈resStack
 *      2）从左向右扫描中缀表达式
 *      3）如果ch为数字 ，将其压入resStack
 *      4）如果ch为运算符
 *          4.1）如果operStack为空或者栈顶为'(' , ch入符号栈
 *          4.2）如果ch优先级高于栈顶运算符，ch 入符号栈
 *          4.3）如果ch优先级小与等于栈顶运算符, 符号栈顶符号入结果栈，再次转到4.1相比较
 *      5）如果ch为'(', 压入符号栈
 *      6) 如果ch为')',则依次弹出符号栈的运算符并压入结果栈，知道遇到'('为止，并舍弃这一对括号/
 *      7) 将operStack 剩余对运算符依次弹出并压入resStack
 *      8) 逆序输出resStake对元素。
 */
public class 中缀转后缀表达式 {
    public static void main(String[] args) {
        //convertToPolandExpression("1 + 2 * ( 7 - 4 ) / 3");
        //convertToPolandExpression("1 + ( ( 2 + 3 ) * 4 ) - 5");
        convertToPolandExpression("10 - 2 * 3 + 4");

    }
    public static void convertToPolandExpression(String expression){
        String[] s = expression.split(" ");
        MyArrayListStack<String> operStack = new MyArrayListStack<>();
        MyArrayListStack<String> resStack = new MyArrayListStack<>();
        List<String> list = Arrays.asList(s);
        System.out.println(list);
        for (String ch : list) {
            // 1. 符合数字 push结果栈
            if (ch.matches("\\d+")){
                resStack.push(ch);
            }
            // 2.符合操作符
            if (operStack.isOper(ch.charAt(0)) ){
                // 2.1 operStack为空  或者 ch 为 (
                while (true){
                    if (operStack.empty() || operStack.peek().charAt(0)=='('){
                        operStack.push(ch);
                        break;
                    }
                    // 2.2 operStack不为空 进行运算符的比较
                    if (operStack.isNotEmpty()){
                        // 2.2.1 如果oper优先级大于栈顶优先级 入符号栈
                        if(operStack.priority(ch.charAt(0))>operStack.priority(operStack.peek().charAt(0))){
                            operStack.push(ch);
                            break;
                            // 2.2.2 如果oper优先级小于等于栈顶优先级 弹出并入结果栈
                        }else {
                            resStack.push(operStack.pop());
                        }
                    }
                }
            }
            // '('
            if (ch.charAt(0)=='('){
                operStack.push(ch);
            }
            if (ch.charAt(0)==')'){
                while(true){
                    if (operStack.peek().charAt(0) == '('){
                        operStack.pop();
                        break;
                    }
                    resStack.push(operStack.pop());
                }
            }
        }
        operStack.display();
        resStack.display();
        System.out.println("进行最后一步操作");
        System.out.println(operStack.getLength());
        while (operStack.isNotEmpty()){
            resStack.push(operStack.pop());
        }
        if (operStack.empty()){
            System.out.println("[]");
        }
        resStack.display();
        resStack.outPutReverse();
    }

}
